W12. Построение Томпсона, алгоритм Клини, иерархия Хомского и вычислимость

1. Краткое содержание

1.1 Построение Томпсона: RegExp → ε-NFSA

1.1.1 Мотивация и обзор

Для RegExp над алфавитом часто нужно вычислительное устройство — конечный автомат, который принимает ровно тот язык, который задаёт выражение. Построение Томпсона (Thompson’s Construction) — классический алгоритм, который превращает любое RegExp в эквивалентный ε-недетерминированный конечный автомат (ε-NFSA). Полученный автомат затем можно использовать для сопоставления строк с исходным RegExp; именно так внутри устроены большинство regex engines.

Алгоритм работает рекурсивно: RegExp разбивается на подвыражения, для каждого строится фрагмент автомата, а фрагменты собираются по фиксированным правилам композиции. Каждое подвыражение \(r\) даёт автомат \(N(r)\) с ровно одним начальным и одним принимающим состоянием (без входящих в начальное и исходящих из принимающего переходов «снаружи» фрагмента). Такая дисциплина структуры упрощает рекурсивную склейку.

1.1.2 Базовые правила

Есть два базовых случая для атомарных регулярных выражений.

Пустое выражение \(\epsilon\). RegExp \(\epsilon\) (распознаёт только пустую строку) превращается в двухсостоятельный автомат: начальное состояние \(q\) и принимающее \(f\), соединённые одним \(\epsilon\)-переходом.

Правило Томпсона для ε: один ε-переход

Один символ \(a\). Символ \(a\) входного алфавита превращается в двухсостоятельный автомат с одним переходом по \(a\) из \(q\) в \(f\).

Правило Томпсона для одного символа a

1.1.3 Правила композиции

Пусть для подвыражений \(s\) и \(t\) построены автоматы \(N(s)\) и \(N(t)\). Три правила покрывают все составные выражения.

Конкатенация \(st\). Принимающее состояние \(N(s)\) сливается с (или соединяется \(\epsilon\)-переходом с) начальным состоянием \(N(t)\). Итоговый автомат начинается там же, где \(N(s)\), и принимает там же, где \(N(t)\). Неформально: сначала читается строка из \(L(s)\), затем строка из \(L(t)\).

Правило Томпсона для конкатенации st: два фрагмента соединяются конец-к-началу

Объединение \(s\,|\,t\). Вводится новое начальное состояние \(q\) с двумя \(\epsilon\)-переходами в начала \(N(s)\) и \(N(t)\). Вводится новое принимающее \(f\), и из принимающих состояний обоих фрагментов идут \(\epsilon\)-переходы в \(f\). Автомат недетерминированно выбирает, какую ветвь развивать.

Правило Томпсона для объединения s|t: новое начало ветвится, обе ветки сходятся в новое принимающее

Звезда Клини \(s^*\). Вводятся новые \(q\) (старт) и \(f\) (принимающее состояние). \(\epsilon\)-переход соединяет \(q\) напрямую с \(f\) (ноль повторений). \(\epsilon\)-переход ведёт из \(q\) в начало \(N(s)\), а из принимающего \(N(s)\) — обратно в начало \(N(s)\) (повторения) и вперёд в \(f\).

Правило Томпсона для звезды Клини s*: петля с конца N(s) к началу плюс обход для нуля повторений

1.1.4 Свойства построения

У ε-NFSA, полученного построением Томпсона, есть полезные структурные свойства: не более \(2n\) состояний для выражения длины \(n\); из каждого состояния не более двух исходящих \(\epsilon\)-переходов; ни один \(\epsilon\)-переход не входит в общее начальное и не выходит из общего принимающего. Это гарантирует корректность шагов композиции на каждом уровне рекурсии.

1.2 Алгоритм Клини: от FSA к регулярному выражению

1.2.1 Обзор

Обратная задача — по конечному автомату найти регулярное выражение для его языка — решается алгоритмом Клини (Kleene’s Algorithm) (в вариантах его называют также алгоритмом исключения состояний). Дан FSA \(M = (Q, A, \delta, q_0, F)\) с состояниями \(Q = \{q_0, q_1, \ldots, q_n\}\); алгоритм систематически вычисляет для каждой пары \((i,j)\) и каждого \(k\) множество \(R_{ij}^{k}\):

\[R_{ij}^{k} = \text{все строки, по которым } M \text{ переходит из } q_i \text{ в } q_j \text{ без прохода через состояния с индексом } > k\]

Каждое такое множество представляется регулярным выражением. Выражения вычисляются по шагам для \(k = -1, 0, 1, \ldots, n\).

Так как ни одно состояние не имеет индекса больше \(n\), выражение \(R_{0j}^{n}\) описывает все строки, ведущие из старта \(q_0\) в \(q_j\) без ограничения на промежуточные состояния. Если \(F = \{q_{f_1}, q_{f_2}, \ldots\}\) — множество принимающих, то:

\[L(M) = R_{0f_1}^{n} \,|\, R_{0f_2}^{n} \,|\, \cdots\]

1.2.2 Начальные выражения (\(k = -1\))

При \(k = -1\) пути не используют промежуточные состояния — только прямые переходы:

\[R_{ij}^{-1} = a_1 \mid a_2 \mid \cdots \mid a_m \qquad (i \neq j), \text{ где } \delta(q_i, a_\ell) = q_j \text{ для всех } \ell\]

\[R_{ii}^{-1} = a_1 \mid \cdots \mid a_m \mid \epsilon \qquad (i = j), \text{ где } \delta(q_i, a_\ell) = q_i \text{ для всех } \ell\]

\[R_{ij}^{-1} = \emptyset \qquad \text{если нет прямого перехода из } q_i \text{ в } q_j\]

\(\epsilon\) в случае петли на себя отражает возможность сделать ноль шагов (остаться в \(q_i\)).

1.2.3 Рекурсивный шаг

Когда для всех пар вычислены \(R_{ij}^{k-1}\), следующий уровень:

\[R_{ij}^{k} = R_{ik}^{k-1}\left(R_{kk}^{k-1}\right)^* R_{kj}^{k-1} \;\Big|\; R_{ij}^{k-1}\]

Наглядно: путь из \(q_i\) в \(q_j\) с использованием состояний с индексом не выше \(k\) либо (a) никогда не заходит в \(q_k\) (это \(R_{ij}^{k-1}\)), либо (b) впервые попадает в \(q_k\) по \(R_{ik}^{k-1}\), затем ноль или более раз «крутится» в \(q_k\) через \(\left(R_{kk}^{k-1}\right)^*\), и после последнего ухода из \(q_k\) идёт к \(q_j\) по \(R_{kj}^{k-1}\).

Эта рекуррентная формула — сердце алгоритма; применение для \(k = 0, 1, \ldots, n\) по порядку в итоге даёт \(R_{0j}^{n}\) для каждого принимающего \(q_j\).

1.3 Модели языков: операционные и порождающие

1.3.1 Два основных подхода

Формальные языки можно описывать двумя принципиально разными способами:

• Операционные модели (автоматы) получают входную строку и решают, допустить её или отвергнуть. Это распознаватели или преобразователи. Примеры: FSA, PDA, машина Тьюринга.
• Порождающие модели (грамматики) задают набор правил переписывания, с помощью которых можно вывести (породить) все и только строки языка. Грамматика не «обрабатывает» вход — она порождает выход.

Оба подхода описывают одни и те же объекты (формальные языки), но с противоположных сторон. У каждого свои плюсы: автоматы ближе к реализации, грамматики — к спецификации.

1.3.2 Грамматики в разборе

В построении компиляторов эти перспективы встречаются в разборе (parsing):

• Грамматика (обычно контекстно-свободная или её запись в BNF) задаёт синтаксис языка программирования — как должны выглядеть синтаксически корректные программы.
• Автомат (парсер) обрабатывает исходный код — читает поток лексем и проверяет соответствие грамматике, восстанавливая синтаксическую структуру для следующих фаз компиляции.

Грамматики в общем случае могут быть недетерминированными, но реальные генераторы парсеров (например LL(1), LR(1)) накладывают ограничения на грамматику и используют ограниченный предпросмотр для детерминированного разбора.

1.4 Иерархия Хомского

1.4.1 Классификация грамматик

Ноам Хомский (р. 1928), «отец современной лингвистики», в 1959 году ввёл формальную классификацию грамматик. Он заметил, что грамматики различаются формой продукций, и от формы зависит класс порождаемых языков. Классификация даёт четыре вложенных типа.

Иерархия Хомского: вложенные классы языков, типы грамматик и соответствующие автоматы

Четыре типа образуют строгую иерархию: каждый регулярный язык контекстно-свобод, каждый КСЯ — контекстно-зависим, каждый КЗЯ — рекурсивно перечислим. Вложения строгие — в каждом классе есть языки не из предыдущего.

1.4.2 Формальное определение грамматики

Грамматика — четвёрка \(G = \langle V_N, V_T, P, S \rangle\), где:

• \(V_N\) — конечное множество нетерминалов (переменных);
• \(V_T\) — конечное множество терминалов (алфавит порождаемых строк), не пересекающееся с \(V_N\);
• \(P\) — конечное множество продукций (правил переписывания);
• \(S \in V_N\) — аксиома (стартовый символ).

Вывод — последовательность строк \(\alpha_0 \Rightarrow \alpha_1 \Rightarrow \cdots \Rightarrow \alpha_k\), где на каждом шаге подстрока \(\alpha_i\) заменяется по правилу из \(P\). Язык, порождённый \(G\):

\[L(G) = \{w \in V_T^* \mid S \Rightarrow^* w\}\]

То есть множество всех терминальных цепочек, выводимых из аксиомы.

1.5 Типы грамматик подробнее

1.5.1 Тип 0: неограниченные грамматики

Грамматики типа 0 (общие, неограниченные) накладывают на правила только требование непустоты левой части:

\[\alpha \rightarrow \beta \quad (\alpha \neq \epsilon)\]

И \(\alpha\), и \(\beta\) — произвольные цепочки терминалов и нетерминалов. Запрет \(\epsilon \rightarrow \beta\) не даёт «создавать символы из ничего». Все остальные типы — частные случаи типа 0.

Грамматикам типа 0 соответствуют машины Тьюринга — они порождают в точности рекурсивно перечислимые языки (те, что TM может допустить, хотя на строках вне языка может зациклиться).

1.5.2 Тип 1: контекстно-зависимые грамматики

Грамматики типа 1 (контекстно-зависимые) требуют, чтобы каждое правило имело вид:

\[\alpha A \beta \rightarrow \alpha \gamma \beta\]

где \(A\) — нетерминал, \(\alpha\) и \(\beta\) — (возможно пустые) цепочки, \(\gamma\) — непустая цепочка. Ключевое ограничение: \(\gamma\) непуста — правила не «стирают» нетерминалы (грамматика не сокращающая / монотонная в смысле длины). Термин контекстно-зависимый отражает, что нетерминал \(A\) переписывается только в контексте \(\alpha\) слева и \(\beta\) справа.

Канонический пример — \(L = \{a^n b^n c^n \mid n \geq 1\}\), который не выводится ни одной КС-грамматикой (наглядно: одного стека недостаточно, чтобы одновременно сопоставить \(a\) с \(b\) и \(b\) с \(c\)). Соответствующая машинная модель — линейно ограниченный автомат (LBA) — машина Тьюринга, у которой головка ограничена участком ленты, занятым входом.

Почему «линейно ограничен»? Длина используемой ленты — линейная функция \(f(n) = k \cdot n + c\) от длины входа \(n\). Например, \(f(n) = 2n\) даёт две ячейки на символ входа. Такое ограниченное рабочее пространство соответствует не сокращающему свойству КЗ-грамматик.

1.5.3 Тип 2: контекстно-свободные грамматики

Грамматики типа 2 (КС-грамматики, CFG) требуют, чтобы слева в каждом правиле был ровно один нетерминал:

\[A \rightarrow \gamma\]

где \(A \in V_N\), \(\gamma \in (V_N \cup V_T)^*\). Переписывание \(A\) не зависит от контекста — какие бы символы ни окружали \(A\), применим один и тот же набор правил. В этом смысл «контекстно-свободно».

КС-грамматики критически важны на практике: они эквивалентны форме Бэкуса — Наура (BNF), которой задают синтаксис почти всех языков программирования. Связь обнаружили в 1960 году: язык ALGOL-60, описанный Бэкусом и Науром в BNF, формально совпадает с контекстно-свободными языками Хомского.

BNF записывает правила как <ЛЧ> ::= <ПЧ>, где <ЛЧ> — нетерминал, <ПЧ> — любая последовательность терминалов и нетерминалов. Например, <expr> ::= <expr> + <term> | <term> задаёт выражения как суммы или одиночные слагаемые.

Контекстно-свободные языки распознаются недетерминированными автоматами с магазином (NPDA). Стек даёт ровно «один уровень вложенности», нужный для скобок и языков вида \(a^n b^n\).

1.5.4 Тип 3: регулярные грамматики

Грамматики типа 3 (регулярные) накладывают самые жёсткие ограничения: все правила либо праволинейные, либо леволинейные — но не смешанные в одной грамматике.

Праволинейная грамматика допускает только правила вида:

• \(A \rightarrow xB\) (цепочка терминалов и не более одного нетерминала справа), или
• \(A \rightarrow x\) (только терминалы).

Леволинейная грамматика допускает только:

• \(A \rightarrow Bx\), или
• \(A \rightarrow x\).

Грамматика регулярна, если все продукции праволинейные или все леволинейные; смешивать ориентации в одной грамматике нельзя. Регулярные грамматики порождают в точности регулярные языки — те же, что допускаются конечными автоматами (FSA) и задаются регулярными выражениями.

1.6 Соответствие между грамматиками и автоматами

1.6.1 Регулярные грамматики и FSA эквивалентны

Эквивалентность регулярных грамматик (RG) и FSA конструктивна в обе стороны.

От FSA к RG. Дан FSA \(A = \langle Q, I, \delta, q_0, F \rangle\), построим \(G = \langle V_N, V_T, S, P \rangle\):

• \(V_N = Q\) (каждое состояние — нетерминал);
• \(V_T = I\) (входной алфавит — терминалы);
• \(S = \langle q_0 \rangle\) (начальное состояние — аксиома);
• для каждого перехода \(\delta(q, i) = q'\) добавить правило \(\langle q \rangle \rightarrow i\langle q' \rangle\);
• для каждого \(q' \in F\) добавить \(\langle q' \rangle \rightarrow \epsilon\).

Инвариант: \(\delta^*(q, x) = q'\) тогда и только тогда, когда \(\langle q \rangle \Rightarrow^* x\langle q' \rangle\).

От RG к FSA. Дана \(G = \langle V_N, V_T, S, P \rangle\), построим \(A = \langle Q, I, \delta, q_0, F \rangle\):

• \(Q = V_N \cup \{q_F\}\) (нетерминалы — состояния; добавить отдельное принимающее состояние);
• \(I = V_T\);
• \(q_0 = S\);
• \(F = \{q_F\}\);
• для каждого \(A \rightarrow bC\) добавить \(\delta(A, b) = C\);
• для каждого \(A \rightarrow b\) (без хвостового нетерминала) добавить \(\delta(A, b) = q_F\).

Так подтверждается, что регулярные грамматики, FSA и регулярные выражения — три эквивалентных формализма для одного семейства языков.

1.6.2 КС-грамматики и NPDA эквивалентны

Контекстно-свободные грамматики эквивалентны недетерминированным автоматам с магазином. Доказательство — теоретическое ядро построения компиляторов. Наглядно: NPDA может моделировать левый вывод КС-грамматики, храня текущую сентенциальную форму в стеке. Если на вершине нетерминал \(A\), NPDA недетерминированно применяет одно из правил для \(A\) (заменяя \(A\) в стеке на правую часть). Если на вершине терминал \(a\), NPDA читает входной символ и проверяет совпадение.

Обратно, любой NPDA можно преобразовать в эквивалентную КС-грамматику (это сложнее, но тоже конструктивно). Поэтому:

\[\text{контекстно-свободные языки} = \text{языки, допускаемые NPDA}\]

1.6.3 Неограниченные грамматики и машины Тьюринга эквивалентны

Общие (неограниченные) грамматики и машины Тьюринга задают один и тот же класс языков — рекурсивно перечислимые. По общей грамматике TM может моделировать выводы, недетерминированно применяя продукции. По TM общая грамматика может кодировать смены конфигураций как переписывания. Так закрепляется вершина иерархии Хомского.

1.6.4 Линейно ограниченный автомат

Линейно ограниченный автомат (LBA) — машина Тьюринга с ключевым ограничением: головка чтения/записи остаётся в пределах участка ленты, занятого входной строкой (между маркерами конца [ и ]). Клетки за пределами входа недоступны.

Длина доступной ленты — линейная функция от \(n\) — отсюда название. LBA для входа длины \(n\) использует не более \(c \cdot n\) ячеек при некоторой константе \(c\). Это ограниченное рабочее пространство соответствует не сокращающему свойству КЗ-грамматик. LBA распознают в точности контекстно-зависимые языки.

1.7 Проблема соответствия Поста

1.7.1 Определение

Проблема соответствия Поста (Post Correspondence Problem, PCP), введённая Эмилем Постом в 1946 году, — один из простейших примеров неразрешимой задачи. В теории вычислимости её часто используют как ступеньку для доказательства неразрешимости других задач (сведением к PCP).

Вход: два списка \(A = (w_1, w_2, \ldots, w_k)\) и \(B = (x_1, x_2, \ldots, x_k)\) строк над некоторым алфавитом.

Вопрос: существует ли конечная последовательность индексов \(i_1, i_2, \ldots, i_m\) (каждый в \(\{1, \ldots, k\}\), \(m \geq 1\)) такая, что:

\[w_{i_1} w_{i_2} \cdots w_{i_m} = x_{i_1} x_{i_2} \cdots x_{i_m}\]

То есть конкатенация выбранных строк из \(A\) в этом порядке совпадает с конкатенацией строк из \(B\) в том же порядке. Пара \((w_i, x_i)\) называется парой соответствия.

1.7.2 Задача неразрешима

Не существует алгоритма, который для произвольного входа PCP всегда отвечает, есть ли решение. Иными словами, нет машины Тьюринга, которая по любому экземпляру \((A, B)\) всегда останавливается и выдаёт «да», если решение есть, и «нет», если его нет. PCP неразрешима (как проблема останова), но формулируется проще — без явной отсылки к машинам Тьюринга или программам.

1.8 Теория вычислимости

1.8.1 Два центральных вопроса

Теория вычислений ставит два фундаментальных вопроса:

1. Математический: что вообще можно вычислить? — существует ли механическая процедура для этой задачи?
2. Инженерный: насколько эффективно можно вычислить? — сколько времени или памяти нужно алгоритму?

Теория вычислимости отвечает на первый вопрос. Она изучает пределы механического решения задач: какие задачи разрешимы на любой вычислительной модели и какие нет — независимо от мощности устройства или выделенного времени.

Удобная метафора: теория вычислимости изучает «скорость света» информатики — фундаментальный предел, который не преодолеть вычислением. Как физические законы ограничивают возможное, так и пределы вычислимости ограничивают математически разрешимое.

1.8.2 Тезис Чёрча — Тьюринга

Тезис Чёрча — Тьюринга (Church-Turing Thesis) — центральное утверждение теории вычислимости. Неформально:

Любая функция, которую можно эффективно вычислить конечной пошаговой процедурой, вычислима машиной Тьюринга.

Это тезис, а не теорема: неформальное «эффективно вычислить» не является математическим определением. Тезис нельзя доказать, только подкрепить: у каждой предложенной модели вычислений (λ-исчисление, частично рекурсивные функции, RAM-машины, квантовые компьютеры и т.д.) либо доказана эквивалентность по выразительности машинам Тьюринга, либо строго меньшая мощность.

Практический вывод: чтобы показать, что задачу нельзя решить никаким алгоритмом, достаточно показать, что её не решает машина Тьюринга.

1.8.3 Проблема останова и неразрешимость

Проблема останова — вопрос: для программы \(P\) и входа \(x\), останавливается ли \(P\) на \(x\)? Алан Тьюринг в 1936 году доказал, что в общем случае ни одна машина Тьюринга не решает эту задачу — она неразрешима.

Задача разрешима (её ещё называют рекурсивной или вычислимой), если существует машина Тьюринга, которая:

• останавливается и допускает каждый вход из языка задачи, и
• останавливается и отвергает каждый вход вне языка.

Задача полуразрешима (рекурсивно перечислима), если TM допускает все положительные входы, но на отрицательных может не остановиться.

Задача неразрешима, если ни одна TM не решает её. Неразрешимые задачи существуют; проблема останова и PCP — классические примеры.

Ландшафт разрешимости: вложенные классы вычислительных задач

---

2. Определения

• Построение Томпсона: алгоритм, переводящий любое регулярное выражение в эквивалентный ε-NFSA путём рекурсивного построения фрагментов для подвыражений и склейки по фиксированным правилам конкатенации, объединения и звезды Клини.
• ε-NFSA (ε-недетерминированный конечный автомат): NFSA с \(\epsilon\)-переходами — переходами без чтения входного символа, позволяющими автомату менять состояние «самопроизвольно».
• Алгоритм Клини: алгоритм перевода конечного автомата \(M\) в регулярное выражение путём вычисления для каждой пары состояний \((i,j)\) и каждой границы \(k\) на промежуточные состояния выражения \(R_{ij}^k\) — все пути из \(q_i\) в \(q_j\) через состояния с индексом не больше \(k\).
• Грамматика: четвёрка \(G = \langle V_N, V_T, P, S \rangle\), задающая множество правил переписывания (продукций) над нетерминалами и терминалами, из которых из аксиомы \(S\) выводятся строки языка.
• Вывод: последовательность строк \(\alpha_0 \Rightarrow \alpha_1 \Rightarrow \cdots \Rightarrow \alpha_k\), где на каждом шаге подстрока заменяется по одной продукции. Порождённый язык — множество всех терминальных цепочек, выводимых из \(S\).
• Иерархия Хомского: классификация формальных грамматик (и порождаемых ими языков) на четыре вложенных типа — тип 0 (неограниченные), тип 1 (контекстно-зависимые), тип 2 (контекстно-свободные), тип 3 (регулярные) — с соответствием классам автоматов.
• Неограниченная грамматика (тип 0): грамматика без ограничений на продукции \(\alpha \rightarrow \beta\) кроме \(\alpha \neq \epsilon\). По мощности эквивалентна машинам Тьюринга; порождает рекурсивно перечислимые языки.
• Контекстно-зависимая грамматика (тип 1): правила вида \(\alpha A \beta \rightarrow \alpha \gamma \beta\) (\(\gamma \neq \epsilon\)). Нетерминал \(A\) переписывается в контексте окружающих цепочек. Эквивалентна LBA.
• Контекстно-свободная грамматика (тип 2): правила вида \(A \rightarrow \gamma\) — один нетерминал переписывается в произвольную цепочку независимо от контекста. Эквивалентна недетерминированным автоматам с магазином.
• Форма Бэкуса — Наура (BNF): нотация для КС-грамматик, задающая синтаксис языков программирования в виде правил <нетерминал> ::= <ПЧ>. Формально эквивалентна CFG.
• Регулярная грамматика (тип 3): все правила праволинейные (\(A \rightarrow xB\) или \(A \rightarrow x\)) или все леволинейные (\(A \rightarrow Bx\) или \(A \rightarrow x\)); смешивать ориентации нельзя. Эквивалентна FSA и регулярным выражениям.
• Праволинейная грамматика: каждое правило \(A \rightarrow xB\) или \(A \rightarrow x\); нетерминал (если есть) всегда справа в правой части.
• Леволинейная грамматика: каждое правило \(A \rightarrow Bx\) или \(A \rightarrow x\); нетерминал (если есть) всегда слева в правой части.
• Линейно ограниченный автомат (LBA): машина Тьюринга с головкой, ограниченной ячейками, занятыми входом (между маркерами конца). LBA распознают в точности контекстно-зависимые языки.
• Разбор (parsing): процесс, в котором автомат (парсер) проверяет, что входная строка (программа) удовлетворяет грамматике (спецификации языка), и восстанавливает синтаксическую структуру.
• Проблема соответствия Поста (PCP): задача: по двум спискам строк \(A\) и \(B\) одинаковой длины выяснить, существует ли конечная последовательность индексов, при которой конкатенация выбранных строк из \(A\) совпадает с конкатенацией соответствующих строк из \(B\). PCP неразрешима.
• Теория вычислимости: раздел теоретической информатики о том, какие задачи могут (и не могут) быть решены механической вычислительной процедурой, независимо от времени и памяти.
• Разрешимая задача: существует машина Тьюринга, которая всегда останавливается и корректно отвечает «да» или «нет» на каждый вход.
• Полуразрешимая задача: машина Тьюринга допускает все положительные входы, но на отрицательных может не останавливаться. То же: рекурсивно перечислимая.
• Неразрешимая задача: ни одна машина Тьюринга не решает задачу; не существует алгоритма, верного на всех входах.
• Тезис Чёрча — Тьюринга: утверждение, что всякая интуитивно вычислимая функция вычислима машиной Тьюринга; эквивалентно: машины Тьюринга исчерпывают предел механического вычисления.

---

3. Формулы

• Алгоритм Клини — начальный шаг (\(k = -1\)): \[R_{ij}^{-1} = \begin{cases} a_1 \mid \cdots \mid a_m & i \neq j,\ \delta(q_i, a_\ell) = q_j \\ a_1 \mid \cdots \mid a_m \mid \epsilon & i = j,\ \delta(q_i, a_\ell) = q_i \\ \emptyset & \text{нет прямого перехода из } q_i \text{ в } q_j \end{cases}\]
• Алгоритм Клини — рекурсивный шаг: \[R_{ij}^{k} = R_{ik}^{k-1}\left(R_{kk}^{k-1}\right)^* R_{kj}^{k-1} \;\Big|\; R_{ij}^{k-1}\]
• Язык FSA через Клини: \[L(M) = \bigcup_{q_f \in F} R_{0f}^{n}\]
• Построение Томпсона — объединение: \[N(s\,|\,t): \text{новое начало} \xrightarrow{\epsilon} N(s) \text{ и } \xrightarrow{\epsilon} N(t); \text{ оба принимающих } \xrightarrow{\epsilon} \text{новое принимающее}\]
• Построение Томпсона — звезда Клини: \[N(s^*): \text{новое начало} \xrightarrow{\epsilon} N(s) \xrightarrow{\epsilon} \text{петля назад}; \text{ плюс обход } \xrightarrow{\epsilon} \text{новое принимающее}\]

---

4. Примеры

4.1. Построить ε-NFSA для \((1 \mid 01)^*\) (Лаба 11, Пример 1)

Постройте ε-NFSA для регулярного выражения \((1 \mid 01)^*\) по правилам Томпсона.

Показать решение

Шаг 1 — построить \(N(1)\). Символ \(1\) даёт двухсостоятельный автомат:

N(1): автомат для символа 1

Шаг 2 — построить \(N(0)\). Аналогично для символа \(0\):

N(0): автомат для символа 0

Шаг 3 — построить \(N(01)\) конкатенацией. Слить \(f_0\) с \(q_1\):

N(01): конкатенация N(0) и N(1)

Шаг 4 — построить \(N(1 \mid 01)\) объединением. Новое начальное \(q'\) с \(\epsilon\)-переходами в начала \(N(1)\) и \(N(01)\), новое принимающее состояние \(f\) с \(\epsilon\)-переходами от обоих принимающих состояний:

Итоговый автомат имеет состояния \(\{q', q_1, f_1', q_0, f_0q_1, f_1, f\}\) с:

• \(q' \xrightarrow{\epsilon} q_1 \xrightarrow{1} f_1' \xrightarrow{\epsilon} f\) (ветвь \(N(1)\));
• \(q' \xrightarrow{\epsilon} q_0 \xrightarrow{0} f_0q_1 \xrightarrow{1} f_1 \xrightarrow{\epsilon} f\) (ветвь \(N(01)\)).

Шаг 5 — применить звезду Клини. Новые начальное \(q''\) и принимающее состояние \(f'\):

• \(q'' \xrightarrow{\epsilon} q'\) (вход в автомат объединения);
• \(f \xrightarrow{\epsilon} q'\) (петля для следующего повторения);
• \(q'' \xrightarrow{\epsilon} f'\) (обход при нуле повторений);
• \(f \xrightarrow{\epsilon} f'\) (переход в принимающее состояние после одного или более повторений).

Полный N((1|01)*): ε-NFSA по построению Томпсона

Ответ: ε-NFSA имеет 9 состояний и распознаёт в точности \(L((1 \mid 01)^*)\) — все строки, полученные конкатенацией нуля или более слов из \(\{1, 01\}\).

4.2. Применить алгоритм Клини к двухсостоятельному FSA (Лаба 11, Пример 2)

Найдите регулярное выражение для языка, принимаемого FSA с состояниями \(\{q_0, q_1\}\), где \(q_0\) — и старт, и единственное принимающее, а переходы: \(\delta(q_0, 0) = q_0\), \(\delta(q_0, 1) = q_1\), \(\delta(q_1, 0) = q_0\).

Двухсостоятельный FSA для примера с алгоритмом Клини

Показать решение

Шаг \(k = -1\) (начальные выражения).

Просматриваем каждую пару состояний:

• \(R_{00}^{-1}\): из \(q_0\) в \(q_0\) по прямым переходам. \(\delta(q_0, 0) = q_0\), символ \(0\) — петля. Так как \(i = j\): \(R_{00}^{-1} = 0 \mid \epsilon\).
• \(R_{01}^{-1}\): из \(q_0\) в \(q_1\). \(\delta(q_0, 1) = q_1\): \(R_{01}^{-1} = 1\).
• \(R_{10}^{-1}\): из \(q_1\) в \(q_0\). \(\delta(q_1, 0) = q_0\): \(R_{10}^{-1} = 0\).
• \(R_{11}^{-1}\): из \(q_1\) в \(q_1\), нет петли по символу. При \(i = j\) и отсутствии петель по символам: \(R_{11}^{-1} = \epsilon\).

Шаг \(k = 0\) (разрешено промежуточное \(q_0\)).

Применяем \(R_{ij}^{0} = R_{i0}^{-1}(R_{00}^{-1})^* R_{0j}^{-1} \mid R_{ij}^{-1}\).

• \(R_{00}^{0} = (0 \mid \epsilon)(0 \mid \epsilon)^*(0 \mid \epsilon) \mid (0 \mid \epsilon) = 0^*\)

  Упрощение: \((0 \mid \epsilon)^* = 0^*\), и \((0 \mid \epsilon) \cdot 0^* \cdot (0 \mid \epsilon) \cup (0 \mid \epsilon) = 0^*\). Допускается любое конечное число нулей, в том числе ни одного.

• \(R_{01}^{0} = (0 \mid \epsilon)(0 \mid \epsilon)^* \cdot 1 \mid 1 = 0^*1\)

  Из \(q_0\) в \(q_0\) (с петлями) и затем по \(1\) в \(q_1\).

• \(R_{10}^{0} = 0 \cdot (0 \mid \epsilon)^* \cdot (0 \mid \epsilon) \mid 0 = 00^*\)

  Переход \(0\) из \(q_1\) в \(q_0\), затем опциональные петли в \(q_0\).

• \(R_{11}^{0} = 0(0 \mid \epsilon)^* \cdot 1 \mid \epsilon = 00^*1 \mid \epsilon\)

  Через \(q_0\) по \(0\), петли, обратно в \(q_1\) по \(1\); либо ноль шагов в \(q_1\).

Шаг \(k = 1\) (разрешено промежуточное \(q_1\)).

Единственное принимающее — \(q_0\), нужно \(R_{00}^{1}\). Имеем:

\[R_{00}^{1} = R_{01}^{0}(R_{11}^{0})^* R_{10}^{0} \mid R_{00}^{0}\]

Подстановка:

\[R_{00}^{1} = (0^*1)(00^*1 \mid \epsilon)^*(00^*) \mid 0^*\]

Упрощение: \((00^*1 \mid \epsilon)^* = (00^*1)^*\) (в том числе ноль повторений шаблона \(00^*1\)). Также \(00^* = 0^+\). Следовательно:

\[R_{00}^{1} = 0^*1(00^*1)^*00^* \mid 0^* = 0^*1(00^*1)^*0^+ \mid 0^*\]

Так как \(F = \{q_0\}\) и \(n = 1\) (два состояния с индексами \(0\) и \(1\)), окончательный ответ — \(R_{00}^{1}\):

\[L(M) = 0^*1(0^+1)^*0^+ \mid 0^*\]

Интерпретация: язык состоит из всех строк из \(0\) и \(1\), которые либо (a) содержат только нули (остаёмся в \(q_0\) по петлям), либо (b) содержат хотя бы одну единицу и оканчиваются блоком нулей — строки, которые перед концом возвращаются в \(q_0\).

4.3. Построить ε-NFSA для \(01^*\) (Лаба 11, Задание 1)

По построению Томпсона постройте ε-NFSA для регулярного выражения \(01^*\).

Показать решение

Шаг 1 — \(N(0)\): двухсостоятельный автомат с переходом по \(0\).

Шаг 2 — \(N(1)\): двухсостоятельный автомат с переходом по \(1\).

Шаг 3 — \(N(1^*)\) по звезде Клини. Новые старт \(q_s\) и принимающее состояние \(f_s\):

• \(q_s \xrightarrow{\epsilon} q_1 \xrightarrow{1} f_1 \xrightarrow{\epsilon} q_1\) (петля);
• \(f_1 \xrightarrow{\epsilon} f_s\) (выход);
• \(q_s \xrightarrow{\epsilon} f_s\) (обход при нуле единиц).

Шаг 4 — \(N(01^*)\) конкатенацией. Соединить \(N(0)\) с \(N(1^*)\), слив принимающее состояние \(N(0)\) со стартом \(N(1^*)\):

\[q_0 \xrightarrow{0} f_0/q_s \xrightarrow{\epsilon} q_1 \xrightarrow{1} f_1 \xrightarrow{\epsilon} q_1 \text{ (петля)}, \quad f_1 \xrightarrow{\epsilon} f_s, \quad f_0/q_s \xrightarrow{\epsilon} f_s\]

ε-NFSA для 01*: переход по 0, затем ноль или более переходов по 1

Автомат принимает в точности строки \(\{0, 01, 011, 0111, \ldots\} = \{01^n \mid n \geq 0\}\).

4.4. Построить ε-NFSA для \((0 \mid 1)01\) (Лаба 11, Задание 2)

По построению Томпсона постройте ε-NFSA для \((0 \mid 1)01\).

Показать решение

Шаг 1 — \(N(0 \mid 1)\) объединением. Старт \(q_u\) с \(\epsilon\) в начала \(N(0)\) и \(N(1)\), принимающее состояние \(f_u\) с \(\epsilon\) от обоих принимающих:

\[q_u \xrightarrow{\epsilon} q_0 \xrightarrow{0} f_0 \xrightarrow{\epsilon} f_u, \quad q_u \xrightarrow{\epsilon} q_1 \xrightarrow{1} f_1 \xrightarrow{\epsilon} f_u\]

Шаг 2 — \(N((0 \mid 1)01)\) конкатенацией с \(N(0)\) и затем \(N(1)\).

Цепочка: принимающее состояние \(N(0 \mid 1)\) соединяется со стартом \(N(0)\), тот — с \(N(1)\):

\[\underbrace{q_u \xrightarrow{\epsilon} \{\ldots\} \xrightarrow{\epsilon} f_u}_{N(0|1)} \xrightarrow{\epsilon\ \text{(слияние)}} q_0' \xrightarrow{0} f_0' \xrightarrow{\epsilon\ \text{(слияние)}} q_1' \xrightarrow{1} f_1'\]

Полный автомат: 1. Старт в \(q_u\). 2. Недетерминированно читается \(0\) или \(1\) (фрагмент объединения), достигается \(f_u\). 3. Читается \(0\), достигается промежуточное состояние. 4. Читается \(1\), достигается принимающее состояние \(f_1'\).

Допускаются строки длины 3 вида «\(0\) или \(1\)», затем \(01\): язык \(L = \{001, 101\}\).

4.5. Построить ε-NFSA для \(00(0 \mid 1)^*\) (Лаба 11, Задание 3)

По построению Томпсона постройте ε-NFSA для \(00(0 \mid 1)^*\).

Показать решение

Шаг 1 — два отдельных \(N(0)\) для ведущих двух нулей.

Шаг 2 — \(N(0 \mid 1)\) по правилу объединения (как в задании 2, шаг 1).

Шаг 3 — \(N((0 \mid 1)^*)\) по звезде Клини: \(q_s \xrightarrow{\epsilon} q_u \xrightarrow{\ldots} f_u \xrightarrow{\epsilon} q_u\) (петля) и \(q_s \xrightarrow{\epsilon} f_s\), \(f_u \xrightarrow{\epsilon} f_s\).

Шаг 4 — \(N(00(0 \mid 1)^*)\) конкатенацией \(N(0)\), \(N(0)\) и \(N((0 \mid 1)^*)\):

\[q_{01} \xrightarrow{0} f_{01}/q_{02} \xrightarrow{0} f_{02}/q_s \xrightarrow{\epsilon} N((0\mid1)^*) \text{ с допуском в } f_s\]

ε-NFSA для 00(0|1)*: два ведущих нуля, затем цикл с любым двоичным суффиксом

Допускаются все строки, начинающиеся с \(00\), с любым (в том числе пустым) двоичным продолжением: \(L = \{00w \mid w \in \{0,1\}^*\}\).

4.6. Применить алгоритм Клини к FSA 1 (Лаба 11, Задание 4)

Найдите регулярное выражение для FSA с состояниями \(\{q_0, q_1\}\), единственное принимающее — \(q_1\), переходы: \(\delta(q_0, 1) = q_0\) (петля), \(\delta(q_0, 0) = q_1\), \(\delta(q_1, 0) = q_1\) (петля).

FSA для задания 4: принимающее состояние q₁

Показать решение

Шаг \(k = -1\):

• \(R_{00}^{-1} = 1 \mid \epsilon\) (петля по \(1\) плюс \(\epsilon\) для нуля шагов).
• \(R_{01}^{-1} = 0\) (прямой переход в \(q_1\) по \(0\)).
• \(R_{10}^{-1} = \emptyset\) (нет перехода из \(q_1\) в \(q_0\)).
• \(R_{11}^{-1} = 0 \mid \epsilon\) (петля по \(0\)).

Шаг \(k = 0\) (промежуточное \(q_0\)):

\[R_{01}^{0} = R_{00}^{-1}(R_{00}^{-1})^* R_{01}^{-1} \mid R_{01}^{-1} = (1 \mid \epsilon)(1 \mid \epsilon)^* 0 \mid 0 = 1^*0\]

\[R_{11}^{0} = R_{10}^{-1}(R_{00}^{-1})^* R_{01}^{-1} \mid R_{11}^{-1} = \emptyset \cdot (\ldots) \mid (0 \mid \epsilon) = 0 \mid \epsilon\]

Шаг \(k = 1\) (промежуточное \(q_1\)):

Нужно \(R_{01}^{1}\) (путь от старта \(q_0\) к допуску \(q_1\)):

\[R_{01}^{1} = R_{01}^{0}(R_{11}^{0})^* R_{11}^{0} \mid R_{01}^{0} = 1^*0 \cdot (0 \mid \epsilon)^* \cdot (0 \mid \epsilon) \mid 1^*0 = 1^*00^*\]

Так как \(F = \{q_1\}\): \(L(M) = R_{01}^{1} = 1^*00^*\).

Интерпретация: язык — все строки вида (ноль или более единиц), затем (один или более нулей). Автомат принимает строки из любого числа ведущих единиц и хотя бы одного нуля после них.

4.7. Применить алгоритм Клини к FSA 2 (Лаба 11, Задание 5)

Найдите регулярное выражение для FSA с состояниями \(\{q_0, q_1\}\), старт и единственное принимающее — \(q_0\), переходы: \(\delta(q_0, 0) = q_0\) (петля), \(\delta(q_0, 1) = q_1\), \(\delta(q_1, 0) = q_1\) (петля), \(\delta(q_1, 1) = q_0\).

FSA для задания 5: принимающее состояние q₀

Показать решение

Шаг \(k = -1\):

• \(R_{00}^{-1} = 0 \mid \epsilon\)
• \(R_{01}^{-1} = 1\)
• \(R_{10}^{-1} = 1\)
• \(R_{11}^{-1} = 0 \mid \epsilon\)

Шаг \(k = 0\):

\[R_{00}^{0} = (0 \mid \epsilon)(0 \mid \epsilon)^*(0 \mid \epsilon) \mid (0 \mid \epsilon) = 0^*\]

\[R_{01}^{0} = (0 \mid \epsilon)(0 \mid \epsilon)^* \cdot 1 \mid 1 = 0^*1\]

\[R_{10}^{0} = 1 \cdot (0 \mid \epsilon)^* \cdot (0 \mid \epsilon) \mid 1 = 10^*\]

\[R_{11}^{0} = 1 \cdot (0 \mid \epsilon)^* \cdot 1 \mid (0 \mid \epsilon) = 10^*1 \mid 0 \mid \epsilon\]

Шаг \(k = 1\):

\[R_{00}^{1} = R_{01}^{0}(R_{11}^{0})^* R_{10}^{0} \mid R_{00}^{0}\] \[= 0^*1 \cdot (10^*1 \mid 0 \mid \epsilon)^* \cdot 10^* \mid 0^*\]

Так как \(F = \{q_0\}\): \(L(M) = 0^*1(10^*1 \mid 0)^* 10^* \mid 0^*\).

Интерпретация: автомат находится в \(q_0\) тогда и только тогда, когда прочитано чётное число единиц (и любое число нулей между ними). Язык — в точности все двоичные строки с чётным числом единиц.

4.8. Регулярное выражение для трёхсостоятельного FSA (Домашнее задание 11, Задание 1)

Найдите регулярное выражение для языка FSA с состояниями \(\{q_0, q_1, q_2\}\), старт и единственное принимающее — \(q_0\), переходы: \(\delta(q_0, 1) = q_0\) (петля), \(\delta(q_0, 0) = q_1\), \(\delta(q_1, 0) = q_1\) (петля), \(\delta(q_1, 1) = q_2\), \(\delta(q_2, 0) = q_1\), \(\delta(q_2, 1) = q_1\).

Трёхсостоятельный FSA для задания из домашней работы 1

Показать решение

Шаг \(k = -1\):

• \(R_{00}^{-1} = 1 \mid \epsilon\)
• \(R_{01}^{-1} = 0\)
• \(R_{02}^{-1} = \emptyset\)
• \(R_{10}^{-1} = \emptyset\)
• \(R_{11}^{-1} = 0 \mid \epsilon\)
• \(R_{12}^{-1} = 1\)
• \(R_{20}^{-1} = \emptyset\)
• \(R_{21}^{-1} = 0 \mid 1\) (и \(0\), и \(1\) ведут из \(q_2\) в \(q_1\))
• \(R_{22}^{-1} = \epsilon\)

Шаг \(k = 0\) (разрешено \(q_0\)):

Так как \(R_{10}^{-1} = \emptyset\) и \(R_{20}^{-1} = \emptyset\), пути с промежуточным \(q_0\) из \(q_1\) или \(q_2\) обратно дают \(\emptyset\). Поэтому:

• \(R_{00}^{0} = 1^*\)
• \(R_{01}^{0} = 1^*0\)
• \(R_{02}^{0} = \emptyset\)
• \(R_{10}^{0} = \emptyset\)
• \(R_{11}^{0} = R_{10}^{-1}(R_{00}^{-1})^* R_{01}^{-1} \mid R_{11}^{-1} = \emptyset \mid (0 \mid \epsilon) = 0 \mid \epsilon\)
• \(R_{12}^{0} = R_{10}^{-1}(R_{00}^{-1})^* R_{02}^{-1} \mid R_{12}^{-1} = \emptyset \mid 1 = 1\)
• \(R_{21}^{0} = R_{20}^{-1}(R_{00}^{-1})^* R_{01}^{-1} \mid R_{21}^{-1} = \emptyset \mid (0 \mid 1) = 0 \mid 1\)
• \(R_{22}^{0} = R_{20}^{-1}(R_{00}^{-1})^* R_{02}^{-1} \mid R_{22}^{-1} = \emptyset \mid \epsilon = \epsilon\)

Шаг \(k = 1\) (разрешены \(q_0\) и \(q_1\)):

\(R_{11}^{1} = R_{11}^{0}(R_{11}^{0})^* R_{11}^{0} \mid R_{11}^{0} = (0 \mid \epsilon)(0 \mid \epsilon)^*(0 \mid \epsilon) \mid (0 \mid \epsilon) = 0^*\)

\(R_{12}^{1} = R_{11}^{0}(R_{11}^{0})^* R_{12}^{0} \mid R_{12}^{0} = (0 \mid \epsilon)(0 \mid \epsilon)^* \cdot 1 \mid 1 = 0^*1\)

\(R_{21}^{1} = R_{21}^{0}(R_{11}^{0})^* R_{11}^{0} \mid R_{21}^{0} = (0 \mid 1)(0 \mid \epsilon)^*(0 \mid \epsilon) \mid (0 \mid 1) = (0 \mid 1)0^*\)

\(R_{22}^{1} = R_{21}^{0}(R_{11}^{0})^* R_{12}^{0} \mid R_{22}^{0} = (0 \mid 1)(0 \mid \epsilon)^* \cdot 1 \mid \epsilon = (0 \mid 1)0^*1 \mid \epsilon\)

\(R_{01}^{1} = R_{01}^{0}(R_{11}^{0})^* R_{11}^{0} \mid R_{01}^{0} = 1^*0 \cdot (0 \mid \epsilon)^* \cdot (0 \mid \epsilon) \mid 1^*0 = 1^*00^*\)

\(R_{02}^{1} = R_{01}^{0}(R_{11}^{0})^* R_{12}^{0} \mid R_{02}^{0} = 1^*0 \cdot (0 \mid \epsilon)^* \cdot 1 \mid \emptyset = 1^*00^*1\)

Шаг \(k = 2\) (все состояния; нужно \(R_{00}^{2}\)):

\[R_{00}^{2} = R_{02}^{1}(R_{22}^{1})^* R_{20}^{1} \mid R_{00}^{1}\]

Сначала \(R_{20}^{1}\): \(R_{20}^{1} = R_{21}^{0}(R_{11}^{0})^* R_{10}^{0} \mid R_{20}^{0} = (0 \mid 1)(0 \mid \epsilon)^* \cdot \emptyset \mid \emptyset = \emptyset\)

И \(R_{00}^{1} = R_{01}^{0}(R_{11}^{0})^* R_{10}^{0} \mid R_{00}^{0} = 1^*0 \cdot (0 \mid \epsilon)^* \cdot \emptyset \mid 1^* = 1^*\)

Так как \(R_{20}^{1} = \emptyset\), произведение \(R_{02}^{1}(R_{22}^{1})^* R_{20}^{1} = \emptyset\). Следовательно:

\[R_{00}^{2} = \emptyset \mid 1^* = 1^*\]

Ответ: \(L(M) = 1^*\).

Интерпретация: принимаются только цепочки из единиц (включая пустую). Любой \(0\) сразу уводит из принимающего \(q_0\), и вернуться в \(q_0\) из \(q_1\) или \(q_2\) нельзя: путь \(q_0 \xrightarrow{0} q_1 \xrightarrow{1} q_2 \xrightarrow{0|1} q_1 \xrightarrow{\ldots}\) никогда не возвращается в \(q_0\). Поэтому принимаются только строки из одних единиц.

4.9. Построить ε-NFSA для \((11)^*(0 \mid 1)\) (Домашнее задание 11, Задание 2)

По построению Томпсона постройте ε-NFSA для \((11)^*(0 \mid 1)\).

Показать решение

Шаг 1 — \(N(1)\) (два состояния, переход по \(1\)).

Шаг 2 — \(N(11)\) конкатенацией двух копий \(N(1)\):

\[q_a \xrightarrow{1} f_a/q_b \xrightarrow{1} f_b\]

Шаг 3 — \(N((11)^*)\) по звезде Клини:

Вводим \(q_s\) и \(f_s\):

• \(q_s \xrightarrow{\epsilon} q_a \xrightarrow{1} f_a/q_b \xrightarrow{1} f_b \xrightarrow{\epsilon} q_a\) (петля);
• \(f_b \xrightarrow{\epsilon} f_s\) (выход);
• \(q_s \xrightarrow{\epsilon} f_s\) (обход).

Шаг 4 — \(N(0 \mid 1)\) объединением:

\[q_u \xrightarrow{\epsilon} q_0' \xrightarrow{0} f_0' \xrightarrow{\epsilon} f_u, \quad q_u \xrightarrow{\epsilon} q_1' \xrightarrow{1} f_1' \xrightarrow{\epsilon} f_u\]

Шаг 5 — конкатенация \(N((11)^*)\) и \(N(0 \mid 1)\):

Слить \(f_s\) с \(q_u\). Итоговый автомат имеет 10 состояний.

ε-NFSA для (11)*(0|1): чётное число единиц, затем один бит 0 или 1

Допускаются строки из чётного числа единиц (включая ноль), за которым следует один бит: \(L = \{(11)^n b \mid n \geq 0,\ b \in \{0,1\}\} = \{0, 1, 110, 111, 11110, 11111, \ldots\}\).